﻿typedef int dataType;

typedef struct Stack
{
	dataType* arr;
	int top;//top不仅表示数据的个数 同时还指向最后一个数据的下一块空间
	int capacity;
} Stack;

void initStack(Stack* pst)
{
	assert(pst != NULL);
	pst->arr = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

void printStack(Stack* pst)
{
	assert(pst != NULL);
	if (stackEmpty(pst))
	{
		printf("NULL\n");
		return;
	}
	while (!stackEmpty(pst))
	{
		printf("%d ", pst->arr[pst->top - 1]);
		pst->top--;
	}
	printf("\n");
}

void stackPush(Stack* pst, dataType x)
{
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity ? 2 * pst->capacity : 5;
		//pstΪNULLʱ reallocmallocȼ
		dataType* tmp = realloc(pst->arr, newCapacity * sizeof (dataType));
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		pst->arr = tmp;
		pst->capacity = newCapacity;
	}
	pst->arr[pst->top] = x;
	pst->top++;
}

void stackPop(Stack* pst)
{
	assert(pst != NULL);
	assert(!stackEmpty(pst));
	pst->top--;
}

int stackTop(Stack* pst)
{
	assert(pst != NULL);
	assert(!stackEmpty(pst));
	return pst->arr[pst->top - 1];
}

int stackEmpty(Stack* pst)
{
	assert(pst != NULL);
	return pst->top == 0;
}

int stackSize(Stack* pst)
{
	assert(pst != NULL);
	return pst->top;
}

void destroyStack(Stack* pst)
{
	if (pst == NULL)
		return;
	free(pst->arr);
	pst->arr = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

typedef struct {
	Stack pushST;//用于存放队列push的数据
	Stack popST;//队列pop时 优先pop popST中的数据 popST中没有数据 就将pushST的数据导过来再pop
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* queue = malloc(sizeof (MyQueue));
	initStack(&queue->pushST);//一个接口实现方式的改变不影响另一个接口 就是低耦合
	initStack(&queue->popST);
	return queue;
}

void myQueuePush(MyQueue* obj, int x) {
	stackPush(&obj->pushST, x);
}

int myQueuePop(MyQueue* obj) {
	int ret;
	if (stackEmpty(&obj->popST))
	{
		while (!stackEmpty(&obj->pushST))
		{
			stackPush(&obj->popST, stackTop(&obj->pushST));
			stackPop(&obj->pushST);
		}
	}
	ret = stackTop(&obj->popST);
	stackPop(&obj->popST);
	return ret;
}

int myQueuePeek(MyQueue* obj) {
	int ret;
	if (stackEmpty(&obj->popST))
	{
		while (!stackEmpty(&obj->pushST))
		{
			stackPush(&obj->popST, stackTop(&obj->pushST));
			stackPop(&obj->pushST);
		}
	}
	ret = stackTop(&obj->popST);
	return ret;
}

bool myQueueEmpty(MyQueue* obj) {
	if (stackEmpty(&obj->pushST) && stackEmpty(&obj->popST))
		return true;
	return false;
}

void myQueueFree(MyQueue* obj) {
	destroyStack(&obj->pushST);
	destroyStack(&obj->popST);
	free(obj);
}